#include <iostream>
#include <assert.h>

#include <math.h>
using namespace std;

// 取块的级别，级别存在块的前一个字节处
#define GET_LEVEL(b) (*((uint8_t*)(b) - 1))

class buddy_allocator_t
{
    // 内存块
    struct buddy_block_t
    {
        buddy_block_t *next;
    };
    typedef buddy_block_t* buddy_block_p;

    inline uintptr_t GET_OFFSET(void* b) { return (uintptr_t)(b) - (uintptr_t)this->base; }

    // 最小的内存池大小
    const static unsigned int MIN_POOL_SIZE=1024*1024*64;
    // 最小可分配的块大小
    const unsigned int MIN_BLOCK_SIZE;
    // 最小可分配块的级别
    const unsigned int MIN_LEVEL;

public:
    uint8_t *pool;              // 内存池
    uint8_t *base;              // 内存池可分配的起始地址
    buddy_block_p *freelist;    // freelist数组，每一个slot存放一个freelist，内存块尺寸=2^i，i即是slot的索引。
    int maxlv;                  // 最大级
    int minlv;                  // 最小级

    inline static size_t LEVEL_2_SIZE(int lv) { return 1 << (lv); }

    // 向上取整到2的幂
    static uint64_t _roundup_pot(uint64_t v)
    {
        v--;
        v |= v >> 1;
        v |= v >> 2;
        v |= v >> 4;
        v |= v >> 8;
        v |= v >> 16;
        v |= v >> 32;
        return ++v;
    }

    // 计算大小代表的级别
    int _calc_level(size_t size)
    {
        int lv = MIN_LEVEL;
        size_t sz = 1 << lv;
        while (size > sz) {
            sz <<= 1;
            lv++;
        }
        return lv;
    }

    // 取一个内存块的伙伴内存块：
    // |<---block--->|<---buddy--->|
    // |<---buddy--->|<---block--->|
    buddy_block_t* _get_buddy(buddy_block_t *block, int lv)
    {
        // 取相对地址
        uintptr_t offsetaddr = this->GET_OFFSET(block);
        // 通过xor即可以取到伙伴的地址，比如：
        // 从左孩子取右孩子：offsetaddr=10000, lv=3: buddyaddr = 10000 ^ (1 << 3) = 10000^1000 = 11000
        // 从右孩子取左孩子：offsetaddr=11000, lv=3: buddyaddr = 11000 ^ (1 << 3) = 11000^1000 = 10000
        uintptr_t buddyaddr = offsetaddr ^ (1 << lv);
        // 取绝对地址
        return (buddy_block_t*)((uintptr_t)this->base + buddyaddr);
    }

    // 初始化
    buddy_allocator_t(size_t poolsz, size_t minsz=16) : MIN_BLOCK_SIZE(minsz), MIN_LEVEL(log(MIN_LEVEL)) //16,4
    {
        poolsz = poolsz > MIN_POOL_SIZE ? poolsz : MIN_POOL_SIZE;
        //minsz = minsz > MIN_BLOCK_SIZE ? minsz : MIN_BLOCK_SIZE;
        assert(minsz < poolsz);
        poolsz = (size_t)_roundup_pot(poolsz);
        minsz = (size_t)_roundup_pot(minsz);
        this->maxlv = _calc_level(poolsz);
        this->minlv = _calc_level(minsz);
        // 这里多分配了一个sizeof(void*)，用于将level放到每个分配的block中
        this->pool = (uint8_t*)calloc(poolsz + sizeof(void*), 1);
        this->base = this->pool + sizeof(void*);

        this->freelist = (buddy_block_p*)calloc(this->maxlv + 1, sizeof(buddy_block_p));
        this->freelist[this->maxlv] = (buddy_block_t*)this->base;
    }

    ~buddy_allocator_t()
    {
        free(this->freelist);
        free(this->pool);
    }

    void* alloc(size_t size)
    {
        size += 1;                      // 多1个字节，用于存放level
        int lv = _calc_level(size);     // 得到该块的级别

        // 向后查找可用的内存块，越往后内存块越大
        int i = lv;
        for (;; ++i)
        {
            if (i > this->maxlv)
                return nullptr;
            if (this->freelist[i])
                break;
        }

        // 从链表取出内存块
        buddy_block_t *block = this->freelist[i];
        this->freelist[i] = this->freelist[i]->next;

        // 将内存块一级一级分割，并放入相应的freelist
        buddy_block_t *buddy;
        while(i-- > lv) {
            buddy = this->_get_buddy(block, i);
            this->freelist[i] = buddy;
        }

        // 记录该内存块的level，在free的时候会用到
        // 这个level是放在block的前一个字节的
        GET_LEVEL(block) = lv;
        return block;
    }

    void free(void *p)
    {
        buddy_block_t *block = (buddy_block_t*)p;
        int i = GET_LEVEL(block);

        buddy_block_t *buddy;
        buddy_block_t **list;

        for (;; ++i) {
            // 取当前块的buddy块
            buddy = this->_get_buddy(block, i);

            // 判断buddy块是否有在freelist中
            list = &this->freelist[i];
            while ((*list != nullptr) && (*list != buddy))
                list = &(*list)->next;

            if (*list != buddy)
            {
                // 如果没找到buddy块，将block加入freelist
                block->next = this->freelist[i];
                this->freelist[i] = block;
                return;
            }
            else
            {
                // 如果找到，将block和buddy合并成大块
                block = block < buddy ? block : buddy;
                // 从链表删除，然后继续循环合并块
                *list = (*list)->next;
            }
        }
    }

    // 打印内存情况
    void stat()
    {

        for (int i = this->minlv; i <= this->maxlv; ++i)
        {
            buddy_block_t *block = this->freelist[i];
            size_t sz = LEVEL_2_SIZE(i);
            printf("Lv %-2d (%lu) : ", i, sz);
            while (block)
            {
                uintptr_t offset = GET_OFFSET(block);
                printf("(%lu--%lu), ", offset, offset + sz - 1);
                block = block->next;
            }
            printf("\n");
        }
        printf("========================================\n");
    }
};

int main()
{
    buddy_allocator_t a(1024*1024*64);
    a.stat();
    int* i1=(int*)a.alloc(4);
    *i1=1;
    a.stat();
    cout<<*i1<<endl;
    a.free(i1);
    a.stat();
    return 0;
}
